﻿using System;
using System.Collections;
using OptimalisationFramework.Utilities.Graphs;
using OptimalisationFramework.Interfaces;

namespace OptimalisationFramework.Problems
{
    class TravelingSalesmanProblem : ITrajectorySearch
    {
        private Graph<string, bool, double> original, configuration;
        private double cost;
        private string start;
        private Random r;

        public TravelingSalesmanProblem()
        {
            original = new Graph<string, bool, double>();
            r = new Random((int)DateTime.Now.Ticks);
        }

        public void AddCityConnection(string city1, string city2, double distance)
        {
            if (!original.VertexExists(city1))
            {
                original.AddVertex(city1, false);
            }
            if (!original.VertexExists(city2))
            {
                original.AddVertex(city2, false);
            }

            original.AddEdge(city1, city2, distance);
        }

        // Generate initial solution using the nearest neighbour algorithm
        public ITrajectorySearch GenerateInitialSolution()
        {            
            //NNA(r.Next(0, original.VertexSize));            
            NNA(3);
            return this;
        }


        public bool StopSearch()
        {
            return false;
        }

        public ITrajectorySearch AdjustSolution()
        {
            //Console.WriteLine("E: " + original.GetVertex("Bornem").EdgeSize);
            // replace a connection
            int x = r.Next(0, configuration.VertexSize), y = r.Next(0, configuration.VertexSize);
            while (x==y)
            {
                y = r.Next(0, configuration.VertexSize);
            }
            Vertex<string, bool, double> vxb = configuration[x];
            Vertex<string, bool, double> vxm = configuration.GetVertex(vxb.EdgeEnd(0));
            Vertex<string, bool, double> vxe = configuration.GetVertex(vxm.EdgeEnd(0));

            Vertex<string, bool, double> vyb = configuration[y];            
            Vertex<string, bool, double> vym = configuration.GetVertex(vyb.EdgeEnd(0));
            Vertex<string, bool, double> vye = configuration.GetVertex(vym.EdgeEnd(0));

            if(vym.ID!=vxe.ID &&  vyb.ID!=vxm.ID && vxm.ID!=vye.ID && vxb.ID!=vym.ID) 
            {

                double xb_ym = original.GetVertex(vxb.ID).GetEdge(vym.ID).W,
                       xm_ye = original.GetVertex(vxm.ID).GetEdge(vye.ID).W,
                       yb_xm = original.GetVertex(vyb.ID).GetEdge(vxm.ID).W,
                       ym_xe = original.GetVertex(vym.ID).GetEdge(vxe.ID).W;

                // remove old neighbours
                vxb.RemoveNeighbour(vxm.ID);
                vxm.RemoveNeighbour(vxe.ID);
                vyb.RemoveNeighbour(vym.ID);
                vym.RemoveNeighbour(vye.ID);

                // add new neighbours
                vxb.AddNeighbour(vym.ID, xb_ym);
                vxm.AddNeighbour(vye.ID, xm_ye);
                vyb.AddNeighbour(vxm.ID, yb_xm);
                vym.AddNeighbour(vxe.ID, ym_xe);
            }
            
            return this;
        }

        public void NNA(int startloc)
        {
            ArrayList discovered = new ArrayList(original.VertexSize);
            configuration = new Graph<string, bool, double>();
            ArrayList path = new ArrayList();
            Vertex<string, bool, double> begin = original[startloc];  
            cost = 0;
            Edge<string, bool, double> min;
            start = begin.ID;
            path.Add(begin.ID);
            Console.WriteLine("Start: " + begin.ID);
            configuration.AddVertex(begin.ID, true);
            while (path.Count <= original.VertexSize - 1)
            {
                min = null;
                ArrayList keys = new ArrayList();
                keys.AddRange(begin.Edges.Keys);
                for (int i = 0; i < keys.Count; i++)
                {
                    if (!discovered.Contains(((Edge<string, bool, double>)begin.Edges[keys[i]]).End))
                    {
                        //Console.WriteLine("\tTown: "+((Edge<string, bool, double>)begin.Edges[keys[i]]).End);
                        if ((min == null || min.W > ((Edge<string, bool, double>)begin.Edges[keys[i]]).W) && original[startloc].ID != ((Edge<string, bool, double>)begin.Edges[keys[i]]).End)
                        {
                            min = ((Edge<string, bool, double>)begin.Edges[keys[i]]);
                        }                        
                    }
                }
                configuration.AddVertex(min.End, true);
                configuration.AddEdge(min.Begin, min.End, min.W);
                discovered.Add(min.End);                   
                cost += min.W;
                path.Add(min.End);
                begin = original.GetVertex(min.End);
            }
            configuration.AddEdge(begin.ID, original[startloc].ID, begin.GetEdge(original[startloc].ID).W);            
        }

        public void WritePath()
        {
            Console.Write(start+ " - ");
            Vertex<string, bool, double> next = configuration.GetVertex(configuration.GetVertex(start).EdgeEnd(0));
            while (next.ID != start)
            {
                Console.Write(next.ID + " - ");
                next = configuration.GetVertex(next.EdgeEnd(0));
            }
            Console.WriteLine();
        }

        public void WriteGraph()
        {
            original.WriteGraph();
        }

        public double ObjectifFunction()
        {
            double cost = 0;
            Vertex<string, bool, double> v = configuration.GetVertex(start);
            for (int i = 0; i < configuration.VertexSize; i++)
            {
                foreach (string edge in v.Edges.Keys)
                {
                    cost += ((Edge<string, bool, double>)v.Edges[edge]).W;
                    v = configuration.GetVertex(((Edge<string, bool, double>)v.Edges[edge]).End);
                }
            }
            return cost;
        }

    }
}
